//
//  SortClass.swift
//  SFQuestion
//
//  Created by sr liu on 2021/6/22.
//

import Foundation

class Sort {
    
    //MARK:交换方法
    /// 交换数组中两个下标的值,注意越界
    /// - Parameters:
    ///   - a: 数组
    ///   - x: 第一个位置
    ///   - y: 第二个位置
    func swap(_ a: inout [Int], _ x:Int, _ y:Int) {
        let temp = a[x]
        a[x] = a[y]
        a[y] = temp
    }
    //MARK: --------------快速排序-----------------
    /// 快排
    /// - Parameters:
    ///   - a: 整形数组
    func QuickSort(_ a: inout [Int]) -> Void {
        let len = a.count
        if len > 1 {
            QSort(&a, 0, len - 1)
        }
    }
    // 快排对于交换的写法有好几种 有的是都循环完了找到位置在交换。k神写法
    // 还有的直接先赋值不交换 最后交换。书上是这样，还有几种尾递归优化 大话结构
    // 写法不同 每一轮中枢得到的结果也不一样，但是整体左小右大是对的
    /// 快速排序递归方法
    /// - Parameters:
    ///   - a: 数组
    ///   - low: 起点
    ///   - high: 终点
    func QSort(_ a: inout [Int], _ low: Int, _ high: Int) -> Void {
        if low < high {
            let partition = Partition(&a, low, high)
            QSort(&a, low, partition - 1)
            QSort(&a, partition + 1, high)
        }
    }
    
    
    func Partition(_ a: inout [Int], _ low:Int, _ high:Int) -> Int {
        var left = low
        var right = high
        //选右边为中枢 应该就是先找左边吧  搜索func partition 215. 数组中的第K个最大元素 有另一个思路
        let pValue = a[low]//选取第一个作为中枢值
        while left < right {
            //找到右侧小于中枢的
            while left < right && a[right] >= pValue {
                right -= 1
            }
            //不必要的交换可以优化
            a.swapAt(left, right)
            
            while left < right && a[left] <= pValue {
                left += 1
            }
            a.swapAt(left, right)
        }
        return left
    }
    
    //GPT建议的优化
    func quickSort(_ a: inout [Int], _ low: Int, _ high: Int) {
        if low < high {
            let pivotIndex = partition(&a, low, high)
            quickSort(&a, low, pivotIndex - 1)
            quickSort(&a, pivotIndex + 1, high)
        }
    }
/**
 当前选的是第一个元素为 pivot（a[low]）：
     •    最坏情况：数组已排序 → O(n²)
     •    更优方案：三数取中（median-of-three） 或 随机 pivot
 
 let pivotIndex = Int.random(in: low...high)
 a.swapAt(low, pivotIndex)
 let pValue = a[low]
 不知道中间的位置，所以还是要从low开始，还是得交换后 取low的位置
 */
    func partition(_ a: inout [Int], _ low: Int, _ high: Int) -> Int {
        let pValue = a[low]
        var left = low
        var right = high

        while left < right {
            //现在left的位置 就是pvalue.
            while left < right && a[right] >= pValue {
                right -= 1
            }
            if left != right {
                a.swapAt(left, right)//交换后，现在right的位置 就是pvalue
            }

            while left < right && a[left] <= pValue {
                left += 1
            }
            if left != right {
                a.swapAt(left, right)//交换后，现在left的位置 就是pvalue
            }
            //其实pvalue一直在跳来跳去
        }
        return left
    }
    //https://cloud.tencent.com/developer/article/2381985 不理解为何不跟基准值比较
    
    
    func partition2(_ a: inout [Int], _ low: Int, _ high: Int) -> Int {
        //三数取中(优化)
            //int keyi = NumBers(a, left, right);
            //Swap(&a[keyi], &a[left]);
        
        var left = low
        var right = high
        var key = left //基准还是取的左侧
        let pValue = a[key]
        
        while left < right {
            
            while left < right && a[right] >= pValue {
                right -= 1
            }

            while left < right && a[left] <= pValue {
                left += 1
            }
            if left < right {
                a.swapAt(left, right)
            }
        }
        a.swapAt(left, key) //基准值交换
        return left
    }
    
    
    // 有些算法 left = right直接复制 最后又给a[left] = pValue  上面用的swap不需要这样
    //MARK: ------------冒泡排序-----------
    //从小到大,最外层趟数理解为确定位置，第一个或者最后一个 取决于内循环。每一次确定位置必须从同一位置开始
    func BubbleSort(_ a: inout [Int]) {
        let n = a.count;
        var swapped = true
        for i in 0..<n-1 {
            print(a)
            guard swapped else {
                break
            }
            swapped = false
            for index in 0..<n-1-i {
                if a[index] > a[index + 1] {
                    swap(&a, index, index + 1)
                    swapped = true
                }
            }
        }
    }
    //优化 记下交换位置
    func BubbleSort2(_ a: inout [Int]) {
        let n = a.count;
        var swapped = true
        var lastIndex = n - 1
        for _ in 0..<n-1 {
            print(a)
            guard swapped else {
                break
            }
            swapped = false
            var tag = 0
            for index in 0..<lastIndex {
                if a[index] > a[index + 1] {
                    swap(&a, index, index + 1)
                    swapped = true
                    tag = index
                }
            }
            lastIndex = tag
        }
    }
    
    //MARK: -二分查找 顺序表
    // log2n
    func BinarySearch(_ arr:[Int], _ value: Int) -> Int {
        if arr.count > 0 {
            var low = 0
            var high = arr.count - 1
            //循环和判断条件 走一遍过程理解好
            while low <= high {
//                let mid = (low + high) / 2
                let mid = low + (high - low) / 2//这样写可以防止边界过大溢出
                if arr[mid] < value {
                    low = mid + 1
                } else if (arr[mid] > value) {
                    high = mid - 1
                } else {
                    return mid
                }
            }
        }
        return -1
    }
    
}
